/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

import java.util.Arrays;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/4/18
 */
//输油管道问题
//    给定n 口油井的位置,编程计算各油井到主管道之间的输油管道最小长度总和.
//    此题为数组的中位数
public class P4_4_1691 {

    public static int test1(int[][] input) {
        dataVerify(input);
        int[] nb = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nb[i] = input[i][1];
        }
        Arrays.sort(nb);
        int mid = nb[nb.length >> 1];
        int sum = 0;
        for (int j = 0; j < nb.length; j++) {
            sum += Math.abs(nb[j] - mid);
        }
        return sum;
    }

    public static int test(int[][] input) {
        dataVerify(input);
        int[] nb = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nb[i] = input[i][1];
        }
        Arrays.sort(nb);
        int maxRange = nb[nb.length - 1] - nb[0];
        int[] sum = new int[maxRange];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < maxRange; i++) {
            int position = nb[0] + i;
            for (int j = 0; j < nb.length; j++) {
                sum[i] += Math.abs(nb[j] - position);
            }
            if (min > sum[i]) {
                min = sum[i];
            }
        }
        return min;
    }

    private static void dataVerify(int[][] input) {

    }

    public static void main(String[] args) {
        System.out.println(test(new int[][] {
                {1, 2},
                {2, 2},
                {1, 3},
                {3, -2},
                {3, 3},
        }));
        System.out.println(test1(new int[][] {
                {1, 2},
                {2, 2},
                {1, 3},
                {3, -2},
                {3, 3},
        }));
    }
}
